#include <stdio.h>
#include <malloc.h>
#include "tree.h"

#define E_OUT_OF_MEMORY -3
#define E_FILE_EMPTY -5

#define MAX_DIF_BYTE 256
#define NUM_MIN_EL 2

#define BITE 1
#define NUM_BITES 1

typedef
struct list {
	int count;
	unsigned char simbol;
	tree * root;
	struct list * next;
} list;

void counter (FILE * input, int * frequency_arr) {
	unsigned char c = 0;
	
	while (fread (&c, BITE, NUM_BITES, input) == 1) {
		frequency_arr[(int)c]++;
	}
	
	fseek(input, 0L, SEEK_SET);
}

int checkFreqArrNotEmpty (int * frequency_arr) {
	int i = 0;
	
	while (i < MAX_DIF_BYTE) {
		if (frequency_arr[i] != 0) {
			break;
		}
		i++;
	}
	
	return (i == MAX_DIF_BYTE) ? E_FILE_EMPTY : 0;
}

int createTreeElement (tree ** el) {
	return ((*el) = (tree *) calloc (1, sizeof(tree))) ? 0 : E_OUT_OF_MEMORY;
}

int createListElement (list ** el, unsigned char simbol, int count) {
	if (!((*el) = (list *) calloc (1, sizeof(list)))) {
		return E_OUT_OF_MEMORY;
	}
	
	(*el)->count = count;
	(*el)->simbol = simbol;
	
	if (createTreeElement (&((*el)->root)) != 0) {
		return E_OUT_OF_MEMORY;
	}
	
	return 0;
}

list * insertListElement (list * head, list * new_el) {
	list * tmp = head;
	
	if (new_el->count < head->count) {
		new_el->next = head;
		return new_el;
	}
	
	while ((tmp->next) && (new_el->count > tmp->next->count)) {
		tmp = tmp->next;
	}
	
	if (! tmp->next) {
		tmp->next = new_el;
		new_el->next = NULL;
	} else {
		new_el->next = tmp->next;
		tmp->next = new_el;
	}
	
	return head;
}

int createList (list ** head, int * frequency_arr) {
	list * new_el = NULL;
	int i = 0;
	
	while (frequency_arr[i] == 0) {
		i++;
	}
	
	if (createListElement (head, (unsigned char)i, frequency_arr[i]) != 0) {
		return E_OUT_OF_MEMORY;
	}
	
	for (i++; i < MAX_DIF_BYTE; i++) {
		if (frequency_arr[i] == 0) {
			continue;
		}
		
		if (createListElement (&new_el, (unsigned char)i, frequency_arr[i]) != 0) {
			return E_OUT_OF_MEMORY;
		}
		
		(*head) = insertListElement (*head, new_el);
	}
	
	return 0;
}

int createBinTree (tree ** root, list * head) {
	list * tmp = head;
	list * new_head = NULL;
	tree * new_el = NULL;
	
	if (! tmp->next) { // if only one element in list
		(*root) = tmp->root;
		(*root)->data = tmp->simbol;
		return 0;
	}
	
	while (tmp->next) {
		if ((! tmp->root->left && ! tmp->root->right) && (! tmp->next->root->left && ! tmp->next->root->right)) {
			if (createTreeElement (&new_el) != 0) {
				return E_OUT_OF_MEMORY;
			}
			tmp->next->root->left = new_el;
			tmp->next->root->left->data = tmp->simbol;
			
			if (createTreeElement (&new_el) != 0) {
				return E_OUT_OF_MEMORY;
			}
			tmp->next->root->right = new_el;
			tmp->next->root->right->data = tmp->next->simbol;
		} else if ((tmp->root->left && tmp->root->right) && (! tmp->next->root->left && ! tmp->next->root->right)) {
			tmp->next->root->left = tmp->root;
			
			if (createTreeElement (&new_el) != 0) {
				return E_OUT_OF_MEMORY;
			}
			tmp->next->root->right = new_el;
			tmp->next->root->right->data = tmp->next->simbol;
		} else if ((! tmp->root->left && ! tmp->root->right) && (tmp->next->root->left && tmp->next->root->right)) {
			if (createTreeElement (&new_el) != 0) {
				return E_OUT_OF_MEMORY;
			}
			new_el->right = tmp->next->root;
			tmp->next->root = new_el;
			
			if (createTreeElement (&new_el) != 0) {
				return E_OUT_OF_MEMORY;
			}
			tmp->next->root->left = new_el;
			tmp->next->root->left->data = tmp->simbol;
		} else {
			if (createTreeElement (&new_el) != 0) {
				return E_OUT_OF_MEMORY;
			}
			new_el->left = tmp->root;
			new_el->right = tmp->next->root;
			tmp->next->root = new_el;
		}
		
		tmp->next->count += tmp->count;
		new_head = tmp->next;
		if (new_head->next) {
			new_head = insertListElement (new_head->next, new_head);
			tmp->next = new_head;
			tmp = new_head;
		} else {
			tmp = tmp->next;
		}
	}
	
	(*root) = tmp->root;
	
	return 0;
}

void clearTree (tree ** root) {
	if ((*root)->left) {
		clearTree (&((*root)->left));  // если левый элемент существует, то рассматриваем левое поддерево
	} 
	
	if ((*root)->right) {
		clearTree (&((*root)->right)); // если правый элемент существует, то рассматриваем правое поддерево
	} 
	
	free (*root); // очищаем корень
	
	return;
}

void clearList (list * head) {
	list * tmp = head->next;
	
	while (tmp) {
		free (head);
		head = tmp;
		tmp = head->next;
	}
	free (head);
	
	return;
}

int binTreeBuilder (FILE * input, tree ** root) {
	int * frequency_arr = NULL;
	list * head = NULL;
	tree * el = NULL;
	
	if (! (frequency_arr = (int *) calloc (MAX_DIF_BYTE, sizeof(int)))) { // выделение памяти под частотный массив
		return E_OUT_OF_MEMORY;
	}
	
	counter (input, frequency_arr); // подсчет частот различных байт
	
	if (checkFreqArrNotEmpty (frequency_arr) != 0) { // проверка, что частотный массив не пуст
		return E_FILE_EMPTY;
	}
	
	if (createList (&head, frequency_arr) != 0) { // построение списка
		return E_OUT_OF_MEMORY;
	}
	
	free (frequency_arr);
	
	if (createBinTree (root, head) != 0) {
		return E_OUT_OF_MEMORY;
	}
	
	if (! (*root)->left) {
        if (createTreeElement (&el) != 0) {
			return E_OUT_OF_MEMORY;
		}
        el->data = (*root)->data;
        (*root)->data = 0;
        (*root)->left = el;
        
        if (createTreeElement (&el) != 0) {
			return E_OUT_OF_MEMORY;
		}
        (*root)->right = el;
    }
    
	clearList (head);
	
	return 0;
}
